package io.tec.cloud.algorithm.c15_v20220711;

import java.util.ArrayList;
import java.util.List;

/**
 * 85	15_3	15	3	15并查集及其面试题目	305.岛屿数量II
 * <p>
 * A 2d grid map of m rows and n columns is initially filled with water. We may perform an addLand operation which turns the water at position (row, col) into a land. Given a list of positions to operate, count the number of islands after each addLand operation. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
 * <p>
 * Example:
 * <p>
 * Input: m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]]
 * Output: [1,1,2,3]
 * <p>
 * Explanation:
 * <p>
 * Initially, the 2d grid grid is filled with water. (Assume 0 represents water and 1 represents land).
 * <p>
 * 0 0 0
 * 0 0 0
 * 0 0 0
 * <p>
 * Operation 1: addLand(0, 0) turns the water at grid[0][0] into a land.
 * <p>
 * 1 0 0
 * 0 0 0   Number of islands = 1
 * 0 0 0
 * <p>
 * Operation 2: addLand(0, 1) turns the water at grid[0][1] into a land.
 * <p>
 * 1 1 0
 * 0 0 0   Number of islands = 1
 * 0 0 0
 * <p>
 * Operation 3: addLand(1, 2) turns the water at grid[1][2] into a land.
 * <p>
 * 1 1 0
 * 0 0 1   Number of islands = 2
 * 0 0 0
 * <p>
 * Operation 4: addLand(2, 1) turns the water at grid[2][1] into a land.
 * <p>
 * 1 1 0
 * 0 0 1   Number of islands = 3
 * 0 1 0
 * <p>
 * Follow up:
 * <p>
 * Can you do it in time complexity O(k log mn), where k is the length of the positions?
 */
public class Code15_3_NumberOfIslands {

    public static void main(String[] args) {
        int[] arr = {0, 1, 2, 3, 4, 5};
        int i = 0;
        System.out.println(arr[i++]);
        i = 0;
        System.out.println(arr[++i]);
        int j = 1;
        System.out.println(arr[j--]);
        j = 1;
        System.out.println(arr[--j]);
    }

    public static List<Integer> numIslands21(int m, int n, int[][] positions) {

        UnionFind unionFind = new UnionFind(m, n);
        List<Integer> result = new ArrayList<>();
        for (int[] arr : positions) {
            result.add(unionFind.connect(arr[0], arr[1]));
        }
        return result;
    }

    static class UnionFind {
        int[] parent;
        int[] size;
        int[] help;
        int r;
        int c;
        int sets;

        public UnionFind(int m, int n) {
            int length = m + n;
            parent = new int[length];
            size = new int[length];
            help = new int[length];
            r = m;
            c = n;
            sets = 0;
        }


        private int index(int row, int col) {
            return row * c + col;
        }

        public Integer connect(int row, int col) {
            int index = index(row, col);
            if (size[index] == 0) {
                parent[index] = index;
                size[index] = 1;
                sets++;
                union(row - 1, col, row, col);
                union(row + 1, col, row, col);
                union(row, col - 1, row, col);
                union(row, col + 1, row, col);

            }
            return sets;
        }

        private void union(int r1, int c1, int r2, int c2) {
            //  越界检查
            if (r1 < 0 || r1 == r || c1 < 0 || c1 == c || r2 < 0 || r2 == r || c2 < 0 || c2 == c) {
                return;
            }

            int index1 = index(r1, c1);
            int index2 = index(r2, c2);
            if (size[index1] == 0 || size[index2] == 0) {
                return;
            }
            int f1 = father(index1);
            int f2 = father(index2);
            int size1 = size[f1];
            int size2 = size[f2];
            if (size1 > size2) {
                parent[f2] = f1;
                size[f1] = size1 + size2;
            } else {
                parent[f1] = f2;
                size[f2] = size1 + size2;
            }
            sets--;
        }

        private int father(int index) {
            int step = 0;
            while (index != parent[index]) {
                help[step++] = index;
                index = parent[index];
            }
            while (step > 0) {
                parent[help[--step]] = index;
            }
            return index;
        }
    }
}
